推導大 O 階方法

如何分析一個演算法的時間複雜度呢?

推導大 O 階:

1. 用常數 1 取代執行時間中的所有加法常數。
2. 在修改後的執行次數函數中，只保留最階項。
3. 如果最高階項存在且不是 1，則去除語這個項相乘的常數。
   獲得的結果就是大 O 階。

常數階

首先循序結構的時間複雜度。下面這個演算法，也就是剛才的第二種演算法(高斯演算法)，為什麼時間複雜度不是 O(3)，而是 O(1)。

int sum = 0,n = 100; /* 執行一次 */
sum = (1 + n) * n / 2; /* 執行一次 */
printf ("%d", sum); /* 執行一次 */

這個演算法的執行次數函數是 f(n) = 3。根據我們推導大 O 階的方法，第一步就是把常數項 3 改為 1。在保留最高階項時發現，它根本沒有最高階項，所以這個演算法的時間複雜度為 O(1)。

如果這個演算法當中的敘述 sum = (1 + n) * n / 2 有 10 句，即:

int sum = 0, n = 100; * 執行 1 次 */
sum = (1 + n) * n / 2; /* 執行第 1 次 */
sum = (1 + n) * n / 2; /* 執行第 2 次 */
sum = (1 + n) * n / 2; /* 執行第 3 次 */
sum = (1 + n) * n / 2; /* 執行第 4 次 */
sum = (1 + n) * n / 2; /* 執行第 5 次 */
sum = (1 + n) * n / 2; /* 執行第 6 次 */
sum = (1 + n) * n / 2; /* 執行第 7 次 */
sum = (1 + n) * n / 2; /* 執行第 8 次 */
sum = (1 + n) * n / 2; /* 執行第 9 次 */
sum = (1 + n) * n / 2; /* 執行第 10 次 */
printf ("%d", sum); * 執行 1 次 */

事實上無論 n 為多少，上面兩段程式就是 3 次和 12 次執行的差異。這種與問題的大小無關(n 的多少)，執行時間固定的演算法，稱之為具有 O(1) 的時間複雜度，又叫常數階。

換句話說，推導大 O 階時只要抓出對效能影響最大的關鍵項並簡化，像這種執行次數固定、跟資料量大小無關的程式，它的時間複雜度就是常數階 O(1)。

今日的分享就到這囉，我們明天見，掰掰！